Search for: All records

Anchor-based ad-hoc networks utilize hop measurements to generate a virtual coordinate system for topology inference and routing applications. A common problem with such coordinate system is its sensitivity to anchor placement. We present a general formulation to the anchor node selection problem. Then, we relax the optimization problem by deriving an upper-bound of the objective function. We finally propose an iterative algorithm that consists in choosing additional anchor nodes based on the connectivity information provided by the current anchor set. Numerical simulations indicate that our anchor selection method is robust to missing measurements and improves network topology inference and routing performance. 

Learning network topology from partial knowledge of its connectivity is an important objective in practical scenarios of communication networks and social-media networks. Representing such networks as connected graphs, exploring and recovering connectivity information between network nodes can help visualize the network topology and improve network utility. This work considers the use of simple hop distance measurement obtained from a fraction of anchor/source nodes to reconstruct the node connectivity relationship for large scale networks of unknown connection topology. Our proposed approach consists of two steps. We first develop a tree-based search strategy to determine constraints on unknown network edges based on the hop count measurements. We then derive the logical distance between nodes based on principal component analysis (PCA) of the measurement matrix and propose a binary hypothesis test for each unknown edge. The proposed algorithm can effectively improve both the accuracy of connectivity detection and the successful delivery rate in data routing applications.